package com.zdp.leetcodeMiddle;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 组合_77 {
    public static void main(String[] args) {
        组合_77 demo = new 组合_77();
        List<List<Integer>> combine = demo.combine1(4, 2);
        for(List<Integer> temp : combine){
            System.out.println(temp.toString());
        }
    }
    /*
    * 解题思路： 搜索+回溯
    * 与 子集的思路有点类似
    * */
    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        if(k == 0){
            return null;
        }
        List<Integer> temp = new ArrayList<>();
        for(int i=1;i<=n;i++){
            temp.add(i);
            f(i+1,n,k-1,(ArrayList<Integer>) temp);
            temp.remove(temp.size()-1);
        }
        return result;
    }

    public void f(int index,int n,int k,ArrayList<Integer> temp){
        // 剪枝
        if(n-index+1 + temp.size() < k){
            return ;
        }
        if(k==0){
            // 满足条件
            result.add((ArrayList<Integer>)temp.clone());
            return ;
        }
        // 不满足条件
        for(int i=index;i<=n;i++){
            temp.add(i);
            f(i+1,n,k-1,temp);
            temp.remove(temp.size()-1);
        }
    }

    /*
    * 官方的递归： 每个位置只有两个状态 选中和没有被转中
    * */
    public List<List<Integer>> combine1(int n, int k) {
        if(k == 0){
            return null;
        }
        List<Integer> temp = new ArrayList<>();
        dfs(1,n,k,temp);
        return result;
    }
    public void dfs(int index,int n,int k,List<Integer> temp){
        if(temp.size() + n-index+1 < k){
            return ;
        }
        if(temp.size() == k){
            result.add(new ArrayList<Integer>(temp));
            return ;
        }
        // 选中当前位置
        temp.add(index);
        dfs(index+1,n,k,temp);
        temp.remove(temp.size()-1);
        // 不选中当前位置
        dfs(index+1,n,k,temp);
    }
}
